package oj;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LC1178 {
    public List<Integer> findNumOfValidWords(String[] words, String[] puzzles) {
        Map<Integer,Integer> map=new HashMap<>();
        for(String wor:words){
            int two=getBin(wor);
            map.put(two,map.getOrDefault(two,0)+1);
        }
        //查看puzzles中有多少谜底
        List<Integer> list=new ArrayList<>();
        for(String puz:puzzles){
            list.add(getCnt(map,puz));
        }
        return list;

    }
    //看每个谜面有多少个谜底
    //每一位有0、1两种可能，每个谜面有7位，因此除了首字母剩下6位共有2^6种可能，也就是1<<(7-1)种可能
    private int getCnt(Map<Integer,Integer> map,String p){
        int ans=0;
        char[] ps=p.toCharArray();
        int t=ps[0]-'a';
        int m=p.length();
        for(int i=0;i<(1<<(m-1));i++){
            int u=1<<t;
            for(int j=1;j<m;j++){
                if(((i>>(j-1))&1)!=0){
                    u+=1<<(ps[j]-'a');
                }
            }
            if(map.containsKey(u)){
                ans+=map.get(u);
            }
        }
        return ans;
    }
    //将每个字符串转为二进制数表示
    //用一个int的32位表示，只用到低26位
    //状态压缩
    private int getBin(String w){
        int t=0;
        char[] cs=w.toCharArray();
        for(char c:cs){
            int u=c-'a';
            if((t>>u&1)==0){
                t+=1<<u;
            }
        }
        return t;
    }
}
